The invention relates to data processing systems and more particularly to such systems employing a high-speed buffer or cache in combination with a main store that is available to one or more processors.
Data processing systems frequently employ a high-speed auxiliary buffer storage or cache to temporarily hold data or instructions for fast access thus obviating the fetch requests to the slower operating main memory or backing store. Data are transferred to the cache from the main memory after interrogating the cache and finding the requested data missing. The required data are fetched from the backing store to an allotted portion of the cache for both the immediate and future use. Since the backing store is usually much larger than the cache, several efforts have been undertaken to efficiently map data from the backing store into the cache. Four techniques are described in an article by C. J. Conti entitled "Concepts for Buffer Storage" published in the IEEE Computer Group News, March 1969, pages 9-13.
In the first of these, the sector technique, a sector of data from backing store, comprising a large number of blocks, is mapped into any one of the sectors of the cache, one block at a time. The cache is usually capable of holding only a small number of sectors and each cache sector, at any given time, can contain only blocks from within the same sector of the backing store. The logic required to keep track of which data is in cache is simple. This system requires only one tag per sector and one validity bit per block for searching the cache to determine a "hit". Although any sector of the backing store can be transferred into any sector of the cache, each cache sector must be held open for the missing blocks of the stored sector until replaced by a different sector. This approach becomes somewhat cumbersome in the transfer of data and lacks flexibility in the selection of a few necessary data blocks from among several sectors.
In the second technique, that of the direct mapping into cache, only a block of data is transferred per request and it is preassigned to a certain tag address within the cache. If there are n blocks in the cache, then every Nth block from the backing store is preassigned to the same tag address. The concept of grouping blocks into sectors is no longer required. This arrangement is hardware efficient but lacks flexibility. Other cache methods (such as the fourth technique below) expand on this method to add flexibility. A third technique of buffered storage is the fully associative, and in this scheme any data block may be mapped from the backing store to any data block in the cache. Although this obviates the difficulty of contention, either much hardware or much searching time is required since the tags of all data blocks must be searched. In the fourth scheme described, that of set associative, preassigned blocks are mapped into a set of cache locations using the direct mapping technique. Although this scheme reduces much of the hardware required by the fully associative cache, and the problem of contention, it has the disadvantage of requiring a tag address for each stored block. In this respect it can be reduced further without the loss of efficiency.
These previous attempts at cache organization generally have gone to two extremes, they either transferred a surplus of data or provided a large number of tags, using one tag for every data block stored in the cache. Thus, these caches are either inefficient or the number of circuits become complex and their cost is escalated. From another view, the transfer of a sector is frequently too large. There remains a need for an intermediate sized quantity of data that is much smaller than a sector, yet is greater than a typical block and can be associated with one tag address.
It is accordingly a primary object of this invention to provide a buffer storage or set associative cache system of tag and data arrays in which each tag address provides access to a plurality of data blocks in the data array.
Another important object of this invention is to provide a cache arrangement for a data processing system in which the tag array is smaller in proportion to the data array thus permitting improved circuit efficiencies and decreased costs.
Yet another object of this invention is to provide a cache arrangement in which a single tag address is combined with data block identification bits to access one of a plurality of blocks for that tag address.
Still another object of this invention is to provide a cache arrangement which is readily adaptable to a multiprocessor system.
The foregoing objects are obtained in accordance with the invention by providing buffer storage or cache means having tag and data arrays in which each tag array location has associated therewith a plurality of consecutive data array locations each arranged to store a block of data from the same sector of backing store. The group of data blocks are directly mapped into the data array locations but main store sectors are merely associatively mapped. Since the groups of data blocks are directly mapped, each block location, regardless of sector, can be stored only in its preassigned data array location so that during a fetch only the one tag address holding the group identification needs to be searched to determine the presence or absence of the desired block group in the cache. The presence of each individual block within a group is based upon individual validity bits. The search for the desired word in cache is successful, called a "hit", if the block group is present in cache and the particular block required is valid; otherwise, a "miss" is detected. As single blocks of data are fetched from the backing store and transferred to cache, their validity is designated by appropriate validity bits stored in conjunction with the tag words. A replace array can be also used with the set associative sector cache of the invention to define the least recently used tag word and block group for replacement.
Since each tag word can access a plurality of locations in the data array, there is the advantage of less tag storage capacity required, hence, fewer circuits and lower costs. As in the set associative buffer storage, searching of both the tag and data arrays can be done concurrently; thus for a "hit" or a "miss" the designated data block can be either gated or suppressed from the data array. The ability to fetch single blocks from backing store eliminates a significant number of accesses and much of the transfer time heretofore required for larger units of cache-stored data. A further convenience is that of storing the block validity bits with the sector identification in the tag, enabling an earlier determination of the reliability of the information. This arrangement further reduces the number of registers required thereby enabling circuit simplification.